library(data.table)
library(truncnorm)
library(coda)
devtools::install_github("stan-dev/loo")
library(loo)
library(rstan) 
library(shinystan)
library(invgamma)
library(bayesplot)
library(posterior)

devtools::install_github("jfrench/bayesutils")

setwd('/Users/AM/Documents/_CU Masters/2020 fall Bayesian_7393/code/Bayesian_Statistics_Class_Code/Exam_code')
#df1 = load("diamonds_simple.rda")
#rm(df1, diamonds_simple)
df = bayesutils::diamonds_simple

df$lprice = log(df$price)
df$lcarat = log(df$carat)

df_covid = bayesutils::covid_dec4

lq_theta_y = function(sigmaSQ, beta0, beta1, lpr = df$lprice, lcar = df$lcarat) {
  ld = dnorm(beta0, 0, 100, log = TRUE) + 
    dnorm(beta1, 0, 100, log = TRUE) + 
    dinvgamma(sigmaSQ, shape = 0.01, rate = 0.01, log = TRUE) +
    sum(dnorm(lpr, mean = (beta0 + beta1 * lcar), sd = sqrt(sigmaSQ), log = TRUE))
  return(ld)
}

mh = function(B, theta_start) {
  theta = array(0, c((B+1), 3), dimnames = list(c(), c("sigmaSQ", "beta0", "beta1")))
  
  theta[1,1] = theta_start[1]
  theta[1,2] = theta_start[2]
  theta[1,3] = theta_start[3]

  for (i in 2:dim(theta)[1]) {
    
    ###  step for sigmaSQ
    beta0_star = theta[(i-1),2]
    beta1_star = theta[(i-1),3]
    
    sigmaSQ_star = rtruncnorm(n = 1, a=0, b=Inf, mean = theta[(i-1),1], sd = 0.1)

    num_logr = lq_theta_y(sigmaSQ = sigmaSQ_star, beta0 = beta0_star, beta1 = beta1_star) -
      log(dtruncnorm(x = sigmaSQ_star, a=0, b=Inf, mean = theta[(i-1),1], sd = 0.1))
    den_logr = lq_theta_y(sigmaSQ = theta[i-1, 1], beta0 = beta0_star, beta1 = beta1_star) -
      log(dtruncnorm(x = theta[i-1, 1], a=0, b=Inf, mean = sigmaSQ_star, sd = 0.1)) 
## !!! is the mean correct? Should  we use in den_logr mean = sigmaSQ_star or mean = theta[i-1, 1]? 
# check c-componentwise-mh v1 line 68, 72
    logr = num_logr - den_logr
    if (log(runif(1)) <= min(logr, 0)) {
      theta[i,1] = sigmaSQ_star
    } else {
      theta[i,1] = theta[(i - 1), 1]
    }
    
    ###  step for beta0
    beta1_star = theta[(i-1),3] # it is the repeated code, but I need it to keep the interpretability
    sigmaSQ_star = theta[i,1] # update sigmaSQ_star after the Gibbs step for sigmaSQ
    
    beta0_star = rnorm(1, theta[(i-1),2], 0.1) # !!! check the parametrization (0.1 or 0.1^2)
    
    num_logr = lq_theta_y(sigmaSQ = sigmaSQ_star, beta0 = beta0_star, beta1 = beta1_star) -
      dnorm(x = beta0_star, mean = theta[(i-1),2], sd = 0.1, log = TRUE)
    den_logr = lq_theta_y(sigmaSQ = sigmaSQ_star, beta0 = theta[i-1, 2], beta1 = beta1_star) -
      dnorm(x = theta[(i-1),2], mean = beta0_star, sd = 0.1, log = TRUE)
## !!! is the mean correct? Should  we use in den_logr mean = sigmaSQ_star or mean = theta[i-1, 1]? 
# check c-componentwise-mh v1 line 68, 72
    logr = num_logr - den_logr
    if (log(runif(1)) <= min(logr, 0)) {
      theta[i,2] = beta0_star
    } else {
      theta[i,2] = theta[(i - 1), 2]
    }
    
    ###  step for beta1
    sigmaSQ_star = theta[i,1] # it is the repeated code, but I need it to keep the interpretability
    beta0_star = theta[i,2] # update beta0_star after the Gibbs step for beta0

    beta1_star = rnorm(1, theta[(i-1),3], 0.1) # !!! check the parametrization (0.1 or 0.1^2)
    
    num_logr = lq_theta_y(sigmaSQ = sigmaSQ_star, beta0 = beta0_star, beta1 = beta1_star) -
      dnorm(x = beta1_star, mean = theta[(i-1),3], sd = 0.1, log = TRUE)
    den_logr = lq_theta_y(sigmaSQ = sigmaSQ_star, beta0 = beta0_star, beta1 = theta[i-1, 3]) -
      dnorm(x = theta[(i-1),3], mean = beta1_star, sd = 0.1, log = TRUE)
## !!! is the mean correct? Should  we use in den_logr mean = sigmaSQ_star or mean = theta[i-1, 1]? 
# check c-componentwise-mh v1 line 68, 72
    logr = num_logr - den_logr
    if (log(runif(1)) <= min(logr, 0)) {
      theta[i,3] = beta1_star
    } else {
      theta[i,3] = theta[(i - 1), 3]
    }
    
  }
  return(theta)
}

B = 10^5 
keep = (B/2 + 1):(B + 1)
chain1 = mh(B, theta_start = c(0.1, -1, -1))
chain2 = mh(B, theta_start = c(0.3, 0, 0))
chain3 = mh(B, theta_start = c(0.5, -1, 1))
chain4 = mh(B, theta_start = c(0.2, 1, 1))

mc = mcmc.list(mcmc(chain1[keep,]), mcmc(chain2[keep,]),
                 mcmc(chain3[keep,]), mcmc(chain4[keep,]))
summary(mc)

Iterations = 1:50001
Thinning interval = 1 
Number of chains = 4 
Sample size per chain = 50001 

1. Empirical mean and standard deviation for each variable,
   plus standard error of the mean:

          Mean      SD  Naive SE Time-series SE
sigmaSQ 0.1152 0.00925 2.068e-05      6.977e-05
beta0   8.3798 0.02240 5.008e-05      1.647e-04
beta1   1.5064 0.03135 7.011e-05      2.141e-04

2. Quantiles for each variable:

           2.5%    25%    50%    75%  97.5%
sigmaSQ 0.09853 0.1088 0.1145 0.1211 0.1348
beta0   8.33546 8.3649 8.3797 8.3948 8.4234
beta1   1.44522 1.4854 1.5064 1.5276 1.5680
gelman.diag(mc, autoburnin = FALSE)
Potential scale reduction factors:

        Point est. Upper C.I.
sigmaSQ       1.03       1.08
beta0         1.00       1.01
beta1         1.01       1.03

Multivariate psrf

1.03
# extracting the MCMC samples from the soda_fit object
samples = extract(r_fit_A)
ncycles = length(samples[[1]])
T <- length(df$price)

# each row of yrep is a sample from the pp distribution
yrep = matrix(0, ncol = T, nrow = ncycles)
for (i in seq_len(T)) {
  mui = samples$beta0 + samples$beta1 * df$lcarat[i]
  yrep[, i] = rnorm(ncycles, mean = mui, sd = sqrt(samples$sigmaSQ))
}

# approximate posterior predictive density for an observation
# with the same covariates as observation 1
#plot(density(yrep[,1]))
color_scheme_set("red")

# posterior predictive check
y = df$lprice
ppc_hist(y, yrep[sample(1:ncycles, 8),]) + ggtitle("Model A: histogram comparing the response to 8 replicated data sets")



# scatterplot of y vs average yrep
ppc_scatter_avg(y, yrep) + ggtitle("Model A: scatterplot comparing the response to the average replicated data set")


ppc_dens_overlay(y, yrep = yrep[sample(1:ncycles, 100),]) + ggtitle("Model A: density plot comparing the density of the response to the densities of 100 replicated data sets")


ppc_error_scatter_avg(y, yrep = yrep) + ggtitle("Model A: scatter plot comparing the response to the average predictive error")


ppc_intervals(y, yrep = yrep)


ppc_error_scatter_avg_vs_x(y = y, yrep = yrep, x = df$lcarat)

ppc_intervals(y = y, yrep = yrep, x = df$lcarat) + ggtitle("Model A: Posterior predictive intervals to the observed data values") + xlab("log carat") + ylab("log price")

# extracting the MCMC samples from the soda_fit object
samples = extract(r_fit_B)
ncycles = length(samples[[1]])
T <- length(df$price)

# each row of yrep is a sample from the pp distribution
yrep = matrix(0, ncol = T, nrow = ncycles)
for (i in seq_len(T)) {
  mui = samples$beta0 + samples$beta1 * df$carat[i] + samples$beta2 * df$carat[i] * df$carat[i]
  yrep[, i] = rnorm(ncycles, mean = mui, sd = sqrt(samples$sigmaSQ))
}

# approximate posterior predictive density for an observation
# with the same covariates as observation 1
#plot(density(yrep[,1]))
color_scheme_set("green")

# posterior predictive check
y = df$price
ppc_hist(y, yrep[sample(1:ncycles, 8),]) + ggtitle("Model B: histogram comparing the response to 8 replicated data sets")



# scatterplot of y vs average yrep
ppc_scatter_avg(y, yrep) + ggtitle("Model B: scatterplot comparing the response to the average replicated data set")


ppc_dens_overlay(y, yrep = yrep[sample(1:ncycles, 100),]) + ggtitle("Model B: density plot comparing the density of the response to the densities of 100 replicated data sets")


ppc_error_scatter_avg(y, yrep = yrep) + ggtitle("Model B: scatter plot comparing the response to the average predictive error")


ppc_intervals(y = y, yrep = yrep, x = df$carat) + ggtitle("Model B: Posterior predictive intervals to the observed data values") + xlab("carat") + ylab("price")

samples = extract(r_fit_D)
ncycles = length(samples[[1]])
T <- length(df$price)
df$notic = as.integer(df$inclusions == "noticeable")

# each row of yrep is a sample from the pp distribution
yrep = matrix(0, ncol = T, nrow = ncycles)
for (i in seq_len(T)) {
  mui = samples$beta0 + samples$beta1 * df$lcarat[i] + samples$beta2 * df$notic[i]
  yrep[, i] = rlnorm(ncycles, mean = mui, sd = sqrt(samples$sigmaSQ))
}

color_scheme_set("blue")
ppc_intervals_grouped(y = df$price, yrep = yrep, x = df$carat, prob = 0.5, prob_outer = .95, group = df$notic) + ggtitle("Model D: Posterior predictive intervals to the observed data values") + xlab("lcarat") + ylab("price")


find_ep = function(yrep, min = 0.1, max = 2.4, step=0.1) {
  ep = array(0, dim=c((max-min+step)/step, 5), dimnames = list(c(), c("carat_min", "carat_max", "2.5%","Mean","97.5%")))
  n=0
  for (i in seq(min+step, max, by=step)) {
    n=n+1
    subset = ((df$carat>(i-step)) & (df$carat<=i))
    yrep_subset = yrep[,subset]
    ep[n,1] = i-step
    ep[n,2] = i
    q = quantile(yrep_subset, probs = c(0.025, 0.975))
    ep[n,3] = q[[1]]
    ep[n,4] = mean(yrep_subset)
    ep[n,5] = q[[2]]
  }
return(ep)
}

find_ep(yrep)
temp = ppc_intervals_data(y = df$price, yrep = yrep, x = df$lcarat, prob = 0.5, prob_outer = .95, group = df$notic)

```

LS0tCnRpdGxlOiAiNzM5MyBFeGFtIDIgUiBDb2RlIEFuZHJlaSBNYXR2ZWV2IgpvdXRwdXQ6IGh0bWxfbm90ZWJvb2sKLS0tCmBgYHtyIERhdGEgYW5kIHNldCB1cH0KCmxpYnJhcnkoZGF0YS50YWJsZSkKbGlicmFyeSh0cnVuY25vcm0pCmxpYnJhcnkoY29kYSkKZGV2dG9vbHM6Omluc3RhbGxfZ2l0aHViKCJzdGFuLWRldi9sb28iKQpsaWJyYXJ5KGxvbykKbGlicmFyeShyc3RhbikgCmxpYnJhcnkoc2hpbnlzdGFuKQpsaWJyYXJ5KGludmdhbW1hKQpsaWJyYXJ5KGJheWVzcGxvdCkKbGlicmFyeShwb3N0ZXJpb3IpCgpkZXZ0b29sczo6aW5zdGFsbF9naXRodWIoImpmcmVuY2gvYmF5ZXN1dGlscyIpCgpzZXR3ZCgnL1VzZXJzL0FNL0RvY3VtZW50cy9fQ1UgTWFzdGVycy8yMDIwIGZhbGwgQmF5ZXNpYW5fNzM5My9jb2RlL0JheWVzaWFuX1N0YXRpc3RpY3NfQ2xhc3NfQ29kZS9FeGFtX2NvZGUnKQojZGYxID0gbG9hZCgiZGlhbW9uZHNfc2ltcGxlLnJkYSIpCiNybShkZjEsIGRpYW1vbmRzX3NpbXBsZSkKZGYgPSBiYXllc3V0aWxzOjpkaWFtb25kc19zaW1wbGUKCmRmJGxwcmljZSA9IGxvZyhkZiRwcmljZSkKZGYkbGNhcmF0ID0gbG9nKGRmJGNhcmF0KQoKZGZfY292aWQgPSBiYXllc3V0aWxzOjpjb3ZpZF9kZWM0CgpgYGAKCmBgYHtyIFByb2JsZW0gMSBsb2cgZGVuc2l0eSBGdW5jdGlvbn0KCmxxX3RoZXRhX3kgPSBmdW5jdGlvbihzaWdtYVNRLCBiZXRhMCwgYmV0YTEsIGxwciA9IGRmJGxwcmljZSwgbGNhciA9IGRmJGxjYXJhdCkgewogIGxkID0gZG5vcm0oYmV0YTAsIDAsIDEwMCwgbG9nID0gVFJVRSkgKyAKICAgIGRub3JtKGJldGExLCAwLCAxMDAsIGxvZyA9IFRSVUUpICsgCiAgICBkaW52Z2FtbWEoc2lnbWFTUSwgc2hhcGUgPSAwLjAxLCByYXRlID0gMC4wMSwgbG9nID0gVFJVRSkgKwogICAgc3VtKGRub3JtKGxwciwgbWVhbiA9IChiZXRhMCArIGJldGExICogbGNhciksIHNkID0gc3FydChzaWdtYVNRKSwgbG9nID0gVFJVRSkpCiAgcmV0dXJuKGxkKQp9CgpgYGAKCmBgYHtyIFByb2JsZW0gMSBtaCBGdW5jdGlvbn0KCm1oID0gZnVuY3Rpb24oQiwgdGhldGFfc3RhcnQpIHsKICB0aGV0YSA9IGFycmF5KDAsIGMoKEIrMSksIDMpLCBkaW1uYW1lcyA9IGxpc3QoYygpLCBjKCJzaWdtYVNRIiwgImJldGEwIiwgImJldGExIikpKQogIAogIHRoZXRhWzEsMV0gPSB0aGV0YV9zdGFydFsxXQogIHRoZXRhWzEsMl0gPSB0aGV0YV9zdGFydFsyXQogIHRoZXRhWzEsM10gPSB0aGV0YV9zdGFydFszXQoKICBmb3IgKGkgaW4gMjpkaW0odGhldGEpWzFdKSB7CiAgICAKICAgICMjIyAgc3RlcCBmb3Igc2lnbWFTUQogICAgYmV0YTBfc3RhciA9IHRoZXRhWyhpLTEpLDJdCiAgICBiZXRhMV9zdGFyID0gdGhldGFbKGktMSksM10KICAgIAogICAgc2lnbWFTUV9zdGFyID0gcnRydW5jbm9ybShuID0gMSwgYT0wLCBiPUluZiwgbWVhbiA9IHRoZXRhWyhpLTEpLDFdLCBzZCA9IDAuMSkKCiAgICBudW1fbG9nciA9IGxxX3RoZXRhX3koc2lnbWFTUSA9IHNpZ21hU1Ffc3RhciwgYmV0YTAgPSBiZXRhMF9zdGFyLCBiZXRhMSA9IGJldGExX3N0YXIpIC0KICAgICAgbG9nKGR0cnVuY25vcm0oeCA9IHNpZ21hU1Ffc3RhciwgYT0wLCBiPUluZiwgbWVhbiA9IHRoZXRhWyhpLTEpLDFdLCBzZCA9IDAuMSkpCiAgICBkZW5fbG9nciA9IGxxX3RoZXRhX3koc2lnbWFTUSA9IHRoZXRhW2ktMSwgMV0sIGJldGEwID0gYmV0YTBfc3RhciwgYmV0YTEgPSBiZXRhMV9zdGFyKSAtCiAgICAgIGxvZyhkdHJ1bmNub3JtKHggPSB0aGV0YVtpLTEsIDFdLCBhPTAsIGI9SW5mLCBtZWFuID0gc2lnbWFTUV9zdGFyLCBzZCA9IDAuMSkpIAojIyAhISEgaXMgdGhlIG1lYW4gY29ycmVjdD8gU2hvdWxkICB3ZSB1c2UgaW4gZGVuX2xvZ3IgbWVhbiA9IHNpZ21hU1Ffc3RhciBvciBtZWFuID0gdGhldGFbaS0xLCAxXT8gCiMgY2hlY2sgYy1jb21wb25lbnR3aXNlLW1oIHYxIGxpbmUgNjgsIDcyCiAgICBsb2dyID0gbnVtX2xvZ3IgLSBkZW5fbG9ncgogICAgaWYgKGxvZyhydW5pZigxKSkgPD0gbWluKGxvZ3IsIDApKSB7CiAgICAgIHRoZXRhW2ksMV0gPSBzaWdtYVNRX3N0YXIKICAgIH0gZWxzZSB7CiAgICAgIHRoZXRhW2ksMV0gPSB0aGV0YVsoaSAtIDEpLCAxXQogICAgfQogICAgCiAgICAjIyMgIHN0ZXAgZm9yIGJldGEwCiAgICBiZXRhMV9zdGFyID0gdGhldGFbKGktMSksM10gIyBpdCBpcyB0aGUgcmVwZWF0ZWQgY29kZSwgYnV0IEkgbmVlZCBpdCB0byBrZWVwIHRoZSBpbnRlcnByZXRhYmlsaXR5CiAgICBzaWdtYVNRX3N0YXIgPSB0aGV0YVtpLDFdICMgdXBkYXRlIHNpZ21hU1Ffc3RhciBhZnRlciB0aGUgR2liYnMgc3RlcCBmb3Igc2lnbWFTUQogICAgCiAgICBiZXRhMF9zdGFyID0gcm5vcm0oMSwgdGhldGFbKGktMSksMl0sIDAuMSkgIyAhISEgY2hlY2sgdGhlIHBhcmFtZXRyaXphdGlvbiAoMC4xIG9yIDAuMV4yKQogICAgCiAgICBudW1fbG9nciA9IGxxX3RoZXRhX3koc2lnbWFTUSA9IHNpZ21hU1Ffc3RhciwgYmV0YTAgPSBiZXRhMF9zdGFyLCBiZXRhMSA9IGJldGExX3N0YXIpIC0KICAgICAgZG5vcm0oeCA9IGJldGEwX3N0YXIsIG1lYW4gPSB0aGV0YVsoaS0xKSwyXSwgc2QgPSAwLjEsIGxvZyA9IFRSVUUpCiAgICBkZW5fbG9nciA9IGxxX3RoZXRhX3koc2lnbWFTUSA9IHNpZ21hU1Ffc3RhciwgYmV0YTAgPSB0aGV0YVtpLTEsIDJdLCBiZXRhMSA9IGJldGExX3N0YXIpIC0KICAgICAgZG5vcm0oeCA9IHRoZXRhWyhpLTEpLDJdLCBtZWFuID0gYmV0YTBfc3Rhciwgc2QgPSAwLjEsIGxvZyA9IFRSVUUpCiMjICEhISBpcyB0aGUgbWVhbiBjb3JyZWN0PyBTaG91bGQgIHdlIHVzZSBpbiBkZW5fbG9nciBtZWFuID0gc2lnbWFTUV9zdGFyIG9yIG1lYW4gPSB0aGV0YVtpLTEsIDFdPyAKIyBjaGVjayBjLWNvbXBvbmVudHdpc2UtbWggdjEgbGluZSA2OCwgNzIKICAgIGxvZ3IgPSBudW1fbG9nciAtIGRlbl9sb2dyCiAgICBpZiAobG9nKHJ1bmlmKDEpKSA8PSBtaW4obG9nciwgMCkpIHsKICAgICAgdGhldGFbaSwyXSA9IGJldGEwX3N0YXIKICAgIH0gZWxzZSB7CiAgICAgIHRoZXRhW2ksMl0gPSB0aGV0YVsoaSAtIDEpLCAyXQogICAgfQogICAgCiAgICAjIyMgIHN0ZXAgZm9yIGJldGExCiAgICBzaWdtYVNRX3N0YXIgPSB0aGV0YVtpLDFdICMgaXQgaXMgdGhlIHJlcGVhdGVkIGNvZGUsIGJ1dCBJIG5lZWQgaXQgdG8ga2VlcCB0aGUgaW50ZXJwcmV0YWJpbGl0eQogICAgYmV0YTBfc3RhciA9IHRoZXRhW2ksMl0gIyB1cGRhdGUgYmV0YTBfc3RhciBhZnRlciB0aGUgR2liYnMgc3RlcCBmb3IgYmV0YTAKCiAgICBiZXRhMV9zdGFyID0gcm5vcm0oMSwgdGhldGFbKGktMSksM10sIDAuMSkgIyAhISEgY2hlY2sgdGhlIHBhcmFtZXRyaXphdGlvbiAoMC4xIG9yIDAuMV4yKQogICAgCiAgICBudW1fbG9nciA9IGxxX3RoZXRhX3koc2lnbWFTUSA9IHNpZ21hU1Ffc3RhciwgYmV0YTAgPSBiZXRhMF9zdGFyLCBiZXRhMSA9IGJldGExX3N0YXIpIC0KICAgICAgZG5vcm0oeCA9IGJldGExX3N0YXIsIG1lYW4gPSB0aGV0YVsoaS0xKSwzXSwgc2QgPSAwLjEsIGxvZyA9IFRSVUUpCiAgICBkZW5fbG9nciA9IGxxX3RoZXRhX3koc2lnbWFTUSA9IHNpZ21hU1Ffc3RhciwgYmV0YTAgPSBiZXRhMF9zdGFyLCBiZXRhMSA9IHRoZXRhW2ktMSwgM10pIC0KICAgICAgZG5vcm0oeCA9IHRoZXRhWyhpLTEpLDNdLCBtZWFuID0gYmV0YTFfc3Rhciwgc2QgPSAwLjEsIGxvZyA9IFRSVUUpCiMjICEhISBpcyB0aGUgbWVhbiBjb3JyZWN0PyBTaG91bGQgIHdlIHVzZSBpbiBkZW5fbG9nciBtZWFuID0gc2lnbWFTUV9zdGFyIG9yIG1lYW4gPSB0aGV0YVtpLTEsIDFdPyAKIyBjaGVjayBjLWNvbXBvbmVudHdpc2UtbWggdjEgbGluZSA2OCwgNzIKICAgIGxvZ3IgPSBudW1fbG9nciAtIGRlbl9sb2dyCiAgICBpZiAobG9nKHJ1bmlmKDEpKSA8PSBtaW4obG9nciwgMCkpIHsKICAgICAgdGhldGFbaSwzXSA9IGJldGExX3N0YXIKICAgIH0gZWxzZSB7CiAgICAgIHRoZXRhW2ksM10gPSB0aGV0YVsoaSAtIDEpLCAzXQogICAgfQogICAgCiAgfQogIHJldHVybih0aGV0YSkKfQoKYGBgCgpgYGB7ciBQcm9ibGVtIDEgbWggUnVufQoKQiA9IDEwXjUgCmtlZXAgPSAoQi8yICsgMSk6KEIgKyAxKQpjaGFpbjEgPSBtaChCLCB0aGV0YV9zdGFydCA9IGMoMC4xLCAtMSwgLTEpKQpjaGFpbjIgPSBtaChCLCB0aGV0YV9zdGFydCA9IGMoMC4zLCAwLCAwKSkKY2hhaW4zID0gbWgoQiwgdGhldGFfc3RhcnQgPSBjKDAuNSwgLTEsIDEpKQpjaGFpbjQgPSBtaChCLCB0aGV0YV9zdGFydCA9IGMoMC4yLCAxLCAxKSkKCm1jID0gbWNtYy5saXN0KG1jbWMoY2hhaW4xW2tlZXAsXSksIG1jbWMoY2hhaW4yW2tlZXAsXSksCiAgICAgICAgICAgICAgICAgbWNtYyhjaGFpbjNba2VlcCxdKSwgbWNtYyhjaGFpbjRba2VlcCxdKSkKc3VtbWFyeShtYykKCmBgYAoKYGBge3IgUHJvYmxlbSAyIHRvIGFzc2VzcyB0aGUgY29udmVyZ2VuY2V9CgprZWVwID0gKEIvMiArIDE5MDAxKTooQi8yICsgMjAwMDEpCgptYyA9IG1jbWMubGlzdChtY21jKGNoYWluMVtrZWVwLF0pLCBtY21jKGNoYWluMltrZWVwLF0pLAogICAgICAgICAgICAgICAgIG1jbWMoY2hhaW4zW2tlZXAsXSksIG1jbWMoY2hhaW40W2tlZXAsXSkpCmNvZGE6OnRyYWNlcGxvdChtYykKY29kYTo6YXV0b2NvcnIucGxvdChtYywgbGFnLm1heCA9IDEwMCwgYXV0by5sYXlvdXQgPSBUUlVFKQpnZWxtYW4uZGlhZyhtYywgYXV0b2J1cm5pbiA9IEZBTFNFKQpnZXdla2UuZGlhZyhtYykKCmBgYAoKYGBge3IgUHJvYmxlbSAzIE1vZGVsIEEsIGluY2x1ZGU9RkFMU0V9CnN0YW5fbW9kX0EgPSAiCmRhdGEgewogIGludCBUOwogIHZlY3RvcltUXSBscHI7ICAgIC8vIGxvZyBwcmljZSAKICB2ZWN0b3JbVF0gbGNhcjsgICAvLyBsb2cgY2FyYXQgCiAgcmVhbDxsb3dlcj0wPiB2OyAgLy8gc2FtcGxlIHZhcmlhbmNlIG9mIGxvZyBwcmljZSAKCn0KCnBhcmFtZXRlcnMgewogIHJlYWw8bG93ZXI9MD4gc2lnbWFTUTsKICByZWFsIGJldGEwOwogIHJlYWwgYmV0YTE7Cn0KCnRyYW5zZm9ybWVkIHBhcmFtZXRlcnMgewogIHZlY3RvcltUXSBtdTsKICBmb3IgKGkgaW4gMTpUKSB7CiAgICBtdVtpXSA9IGJldGEwICsgYmV0YTEgKiBsY2FyW2ldOwogIH0KCn0KCm1vZGVsIHsKICBzaWdtYVNRIH4gaW52X2dhbW1hKDAuMDEsIDAuMDEpOwogIGJldGEwIH4gbm9ybWFsKDAsIDEwMCk7CiAgYmV0YTEgfiBub3JtYWwoMCwgMTAwKTsKCiAgZm9yIChpIGluIDE6VCkKICAgIGxwcltpXSB+IG5vcm1hbChtdVtpXSwgc3FydChzaWdtYVNRKSk7Cn0KZ2VuZXJhdGVkIHF1YW50aXRpZXMgewogIHZlY3RvcltUXSBsb2dfbGlrOwogIHZlY3RvcltUXSB5X3JlcDsKCiAgLy92ZWN0b3JbVF0gbGlrOwogIHJlYWwgUmJzcTsgICAgICAgICAgICAgIC8vIGdvb2RuZXNzLW9mLWZpdAogIFJic3EgPSAxIC0gc2lnbWFTUS92OwogIAogIGZvciAoaSBpbiAxOlQpIHsKICAgIGxvZ19saWtbaV0gPSBub3JtYWxfbHBkZihscHJbaV0gfCBtdVtpXSwgc3FydChzaWdtYVNRKSk7CiAgICB5X3JlcFtpXSA9IG5vcm1hbF9ybmcobXVbaV0sIHNxcnQoc2lnbWFTUSkpOwogICAgLy9saWtbaV0gPSBleHAobG9nX2xpa1tpXSk7CiAgfQoKfQoiCgpUIDwtIGxlbmd0aChkZiRscHJpY2UpCnYgPSB2YXIoZGYkbHByaWNlKQpzZXQuc2VlZCg5MCkKCm1vZGVsX25hbWUgPSAiTW9kZWxfQV8iCnN0YW5fZGF0X0EgPSBsaXN0KFQgPSBULCBscHIgPSBkZiRscHJpY2UsIGxjYXIgPSBkZiRsY2FyYXQsIHYgPSB2KQpyX2ZpdF9BID0gc3Rhbihtb2RlbF9jb2RlID0gc3Rhbl9tb2RfQSwgZGF0YSA9IHN0YW5fZGF0X0EsIAogICAgICAgICAgICAgaXRlciA9IDUwMDAsIGNoYWlucyA9IDQsIAogICAgICAgICAgICAgY29udHJvbCA9IGxpc3QobWF4X3RyZWVkZXB0aCA9IDIxKSkKCiNmaWxlX25hbWUgPSBwYXN0ZShtb2RlbF9uYW1lLCBhcy5jaGFyYWN0ZXIoU3lzLkRhdGUoKSksICIucmRhIiwgc2VwPSIiKQojc2V0d2QoJy9Vc2Vycy9BTS9Eb2N1bWVudHMvX0NVIE1hc3RlcnMvMjAyMCBmYWxsIEJheWVzaWFuXzczOTMvY29kZS9CYXllc2lhbl9TdGF0aXN0aWNzX0NsYXNzX0NvZGUvRXhhbV9jb2RlJykKI3JlYWRSRFMocl9maXQsIGZpbGUgPSAiIikgCiNzYXZlUkRTKHJfZml0LCBmaWxlID0gZmlsZV9uYW1lLCBjb21wcmVzcyA9ICJ4eiIpIAoKc3VtbWFyeShyX2ZpdF9BLCBwYXJzID0gYygic2lnbWFTUSIsICJiZXRhMCIsICJiZXRhMSIpLCBwcm9iID0gYygwLjAyNSwgMC45NzUpKSRzdW1tYXJ5Cgojc3NvIDwtIGxhdW5jaF9zaGlueXN0YW4ocl9maXRfQSkKCmBgYAoKYGBge3IgUHJvYmxlbSAzIE1vZGVsIEIsIGluY2x1ZGU9RkFMU0V9CnN0YW5fbW9kX0IgPSAiCmRhdGEgewogIGludCBUOwogIHZlY3RvcltUXSBwcjsgICAgIC8vIHByaWNlIAogIHZlY3RvcltUXSBjYXI7ICAgIC8vIGNhcmF0IAogIHJlYWw8bG93ZXI9MD4gdjsgIC8vIHNhbXBsZSB2YXJpYW5jZSBvZiBsb2cgcHJpY2UgCgp9CgpwYXJhbWV0ZXJzIHsKICByZWFsPGxvd2VyPTA+IHNpZ21hU1E7CiAgcmVhbCBiZXRhMDsKICByZWFsIGJldGExOwogIHJlYWwgYmV0YTI7Cn0KCnRyYW5zZm9ybWVkIHBhcmFtZXRlcnMgewogIHZlY3RvcltUXSBtdTsKICBmb3IgKGkgaW4gMTpUKSB7CiAgICBtdVtpXSA9IGJldGEwICsgYmV0YTEgKiBjYXJbaV0gKyBiZXRhMiAqIGNhcltpXSAqIGNhcltpXTsKICB9Cgp9Cgptb2RlbCB7CiAgc2lnbWFTUSB+IGludl9nYW1tYSgwLjAxLCAwLjAxKTsKICBiZXRhMCB+IG5vcm1hbCgwLCAxMDApOwogIGJldGExIH4gbm9ybWFsKDAsIDEwMCk7CiAgYmV0YTIgfiBub3JtYWwoMCwgMTAwKTsKCiAgZm9yIChpIGluIDE6VCkKICAgIHByW2ldIH4gbm9ybWFsKG11W2ldLCBzcXJ0KHNpZ21hU1EpKTsKfQoKZ2VuZXJhdGVkIHF1YW50aXRpZXMgewogIHZlY3RvcltUXSB5X3JlcDsKICB2ZWN0b3JbVF0gbG9nX2xpazsKICAvL3ZlY3RvcltUXSBsaWs7CiAgcmVhbCBSYnNxOyAgICAgICAgICAgICAgLy8gZ29vZG5lc3Mtb2YtZml0CiAgUmJzcSA9IDEgLSBzaWdtYVNRL3Y7CiAgCiAgZm9yIChpIGluIDE6VCkgewogICAgbG9nX2xpa1tpXSA9IG5vcm1hbF9scGRmKHByW2ldIHwgbXVbaV0sIHNxcnQoc2lnbWFTUSkpOwogICAgeV9yZXBbaV0gPSBub3JtYWxfcm5nKG11W2ldLCBzcXJ0KHNpZ21hU1EpKTsKCiAgICAvL2xpa1tpXSA9IGV4cChsb2dfbGlrW2ldKTsKICB9Cgp9CiIKClQgPC0gbGVuZ3RoKGRmJHByaWNlKQp2ID0gdmFyKGRmJHByaWNlKQpzZXQuc2VlZCg5MSkKCm1vZGVsX25hbWUgPSAiTW9kZWxfQl8iCnN0YW5fZGF0X0IgPSBsaXN0KFQgPSBULCBwciA9IGRmJHByaWNlLCBjYXIgPSBkZiRjYXJhdCwgdiA9IHYpCnJfZml0X0IgPSBzdGFuKG1vZGVsX2NvZGUgPSBzdGFuX21vZF9CLCBkYXRhID0gc3Rhbl9kYXRfQiwgCiAgICAgICAgICAgICBpdGVyID0gNTAwMCwgY2hhaW5zID0gNCwgCiAgICAgICAgICAgICBjb250cm9sID0gbGlzdChtYXhfdHJlZWRlcHRoID0gMjEpKQoKI2ZpbGVfbmFtZSA9IHBhc3RlKG1vZGVsX25hbWUsIGFzLmNoYXJhY3RlcihTeXMudGltZSgpKSwgIi5yZGEiLCBzZXA9IiIpCiNzZXR3ZCgnL1VzZXJzL0FNL0RvY3VtZW50cy9fQ1UgTWFzdGVycy8yMDIwIGZhbGwgQmF5ZXNpYW5fNzM5My9jb2RlL0JheWVzaWFuX1N0YXRpc3RpY3NfQ2xhc3NfQ29kZS9FeGFtX2NvZGUnKQojc2F2ZVJEUyhyX2ZpdCwgZmlsZSA9IGZpbGVfbmFtZSwgY29tcHJlc3MgPSAieHoiKSAKc3VtbWFyeShyX2ZpdF9CLCBwYXJzID0gYygic2lnbWFTUSIsICJiZXRhMCIsICJiZXRhMSIsICJiZXRhMiIpLCBwcm9iID0gYygwLjAyNSwgMC45NzUpKSRzdW1tYXJ5Cgpzc28gPC0gbGF1bmNoX3NoaW55c3RhbihyX2ZpdF9CKQoKYGBgCgpgYGB7ciBQcm9ibGVtIDQgcHBfY2hlY2sgTW9kZWwgQX0KIyBleHRyYWN0aW5nIHRoZSBNQ01DIHNhbXBsZXMgZnJvbSB0aGUgc29kYV9maXQgb2JqZWN0CnNhbXBsZXMgPSBleHRyYWN0KHJfZml0X0EpCm5jeWNsZXMgPSBsZW5ndGgoc2FtcGxlc1tbMV1dKQpUIDwtIGxlbmd0aChkZiRwcmljZSkKCiMgZWFjaCByb3cgb2YgeXJlcCBpcyBhIHNhbXBsZSBmcm9tIHRoZSBwcCBkaXN0cmlidXRpb24KeXJlcCA9IG1hdHJpeCgwLCBuY29sID0gVCwgbnJvdyA9IG5jeWNsZXMpCmZvciAoaSBpbiBzZXFfbGVuKFQpKSB7CiAgbXVpID0gc2FtcGxlcyRiZXRhMCArIHNhbXBsZXMkYmV0YTEgKiBkZiRsY2FyYXRbaV0KICB5cmVwWywgaV0gPSBybm9ybShuY3ljbGVzLCBtZWFuID0gbXVpLCBzZCA9IHNxcnQoc2FtcGxlcyRzaWdtYVNRKSkKfQoKIyBhcHByb3hpbWF0ZSBwb3N0ZXJpb3IgcHJlZGljdGl2ZSBkZW5zaXR5IGZvciBhbiBvYnNlcnZhdGlvbgojIHdpdGggdGhlIHNhbWUgY292YXJpYXRlcyBhcyBvYnNlcnZhdGlvbiAxCiNwbG90KGRlbnNpdHkoeXJlcFssMV0pKQpjb2xvcl9zY2hlbWVfc2V0KCJyZWQiKQoKIyBwb3N0ZXJpb3IgcHJlZGljdGl2ZSBjaGVjawp5ID0gZGYkbHByaWNlCnBwY19oaXN0KHksIHlyZXBbc2FtcGxlKDE6bmN5Y2xlcywgOCksXSkgKyBnZ3RpdGxlKCJNb2RlbCBBOiBoaXN0b2dyYW0gY29tcGFyaW5nIHRoZSByZXNwb25zZSB0byA4IHJlcGxpY2F0ZWQgZGF0YSBzZXRzIikKCgojIHNjYXR0ZXJwbG90IG9mIHkgdnMgYXZlcmFnZSB5cmVwCnBwY19zY2F0dGVyX2F2Zyh5LCB5cmVwKSArIGdndGl0bGUoIk1vZGVsIEE6IHNjYXR0ZXJwbG90IGNvbXBhcmluZyB0aGUgcmVzcG9uc2UgdG8gdGhlIGF2ZXJhZ2UgcmVwbGljYXRlZCBkYXRhIHNldCIpCgpwcGNfZGVuc19vdmVybGF5KHksIHlyZXAgPSB5cmVwW3NhbXBsZSgxOm5jeWNsZXMsIDEwMCksXSkgKyBnZ3RpdGxlKCJNb2RlbCBBOiBkZW5zaXR5IHBsb3QgY29tcGFyaW5nIHRoZSBkZW5zaXR5IG9mIHRoZSByZXNwb25zZSB0byB0aGUgZGVuc2l0aWVzIG9mIDEwMCByZXBsaWNhdGVkIGRhdGEgc2V0cyIpCgpwcGNfZXJyb3Jfc2NhdHRlcl9hdmcoeSwgeXJlcCA9IHlyZXApICsgZ2d0aXRsZSgiTW9kZWwgQTogc2NhdHRlciBwbG90IGNvbXBhcmluZyB0aGUgcmVzcG9uc2UgdG8gdGhlIGF2ZXJhZ2UgcHJlZGljdGl2ZSBlcnJvciIpCgpwcGNfaW50ZXJ2YWxzKHkgPSB5LCB5cmVwID0geXJlcCwgeCA9IGRmJGxjYXJhdCkgKyBnZ3RpdGxlKCJNb2RlbCBBOiBQb3N0ZXJpb3IgcHJlZGljdGl2ZSBpbnRlcnZhbHMgdG8gdGhlIG9ic2VydmVkIGRhdGEgdmFsdWVzIikgKyB4bGFiKCJsb2cgY2FyYXQiKSArIHlsYWIoImxvZyBwcmljZSIpCmBgYAoKYGBge3IgUHJvYmxlbSA0IHBwX2NoZWNrIE1vZGVsIEJ9CiMgZXh0cmFjdGluZyB0aGUgTUNNQyBzYW1wbGVzIGZyb20gdGhlIHNvZGFfZml0IG9iamVjdApzYW1wbGVzID0gZXh0cmFjdChyX2ZpdF9CKQpuY3ljbGVzID0gbGVuZ3RoKHNhbXBsZXNbWzFdXSkKVCA8LSBsZW5ndGgoZGYkcHJpY2UpCgojIGVhY2ggcm93IG9mIHlyZXAgaXMgYSBzYW1wbGUgZnJvbSB0aGUgcHAgZGlzdHJpYnV0aW9uCnlyZXAgPSBtYXRyaXgoMCwgbmNvbCA9IFQsIG5yb3cgPSBuY3ljbGVzKQpmb3IgKGkgaW4gc2VxX2xlbihUKSkgewogIG11aSA9IHNhbXBsZXMkYmV0YTAgKyBzYW1wbGVzJGJldGExICogZGYkY2FyYXRbaV0gKyBzYW1wbGVzJGJldGEyICogZGYkY2FyYXRbaV0gKiBkZiRjYXJhdFtpXQogIHlyZXBbLCBpXSA9IHJub3JtKG5jeWNsZXMsIG1lYW4gPSBtdWksIHNkID0gc3FydChzYW1wbGVzJHNpZ21hU1EpKQp9CgojIGFwcHJveGltYXRlIHBvc3RlcmlvciBwcmVkaWN0aXZlIGRlbnNpdHkgZm9yIGFuIG9ic2VydmF0aW9uCiMgd2l0aCB0aGUgc2FtZSBjb3ZhcmlhdGVzIGFzIG9ic2VydmF0aW9uIDEKI3Bsb3QoZGVuc2l0eSh5cmVwWywxXSkpCmNvbG9yX3NjaGVtZV9zZXQoImdyZWVuIikKCiMgcG9zdGVyaW9yIHByZWRpY3RpdmUgY2hlY2sKeSA9IGRmJHByaWNlCnBwY19oaXN0KHksIHlyZXBbc2FtcGxlKDE6bmN5Y2xlcywgOCksXSkgKyBnZ3RpdGxlKCJNb2RlbCBCOiBoaXN0b2dyYW0gY29tcGFyaW5nIHRoZSByZXNwb25zZSB0byA4IHJlcGxpY2F0ZWQgZGF0YSBzZXRzIikKCgojIHNjYXR0ZXJwbG90IG9mIHkgdnMgYXZlcmFnZSB5cmVwCnBwY19zY2F0dGVyX2F2Zyh5LCB5cmVwKSArIGdndGl0bGUoIk1vZGVsIEI6IHNjYXR0ZXJwbG90IGNvbXBhcmluZyB0aGUgcmVzcG9uc2UgdG8gdGhlIGF2ZXJhZ2UgcmVwbGljYXRlZCBkYXRhIHNldCIpCgpwcGNfZGVuc19vdmVybGF5KHksIHlyZXAgPSB5cmVwW3NhbXBsZSgxOm5jeWNsZXMsIDEwMCksXSkgKyBnZ3RpdGxlKCJNb2RlbCBCOiBkZW5zaXR5IHBsb3QgY29tcGFyaW5nIHRoZSBkZW5zaXR5IG9mIHRoZSByZXNwb25zZSB0byB0aGUgZGVuc2l0aWVzIG9mIDEwMCByZXBsaWNhdGVkIGRhdGEgc2V0cyIpCgpwcGNfZXJyb3Jfc2NhdHRlcl9hdmcoeSwgeXJlcCA9IHlyZXApICsgZ2d0aXRsZSgiTW9kZWwgQjogc2NhdHRlciBwbG90IGNvbXBhcmluZyB0aGUgcmVzcG9uc2UgdG8gdGhlIGF2ZXJhZ2UgcHJlZGljdGl2ZSBlcnJvciIpCgpwcGNfaW50ZXJ2YWxzKHkgPSB5LCB5cmVwID0geXJlcCwgeCA9IGRmJGNhcmF0KSArIGdndGl0bGUoIk1vZGVsIEI6IFBvc3RlcmlvciBwcmVkaWN0aXZlIGludGVydmFscyB0byB0aGUgb2JzZXJ2ZWQgZGF0YSB2YWx1ZXMiKSArIHhsYWIoImNhcmF0IikgKyB5bGFiKCJwcmljZSIpCmBgYAoKYGBge3IgUHJvYmxlbSA1IE1vZGVsIEMsIGluY2x1ZGU9RkFMU0V9CnN0YW5fbW9kX0MgPSAiCmRhdGEgewogIGludCBUOwogIHZlY3RvcltUXSBwcjsgICAgLy8gIHByaWNlIAogIHZlY3RvcltUXSBsY2FyOyAgIC8vIGxvZyBjYXJhdCAKICByZWFsPGxvd2VyPTA+IHY7ICAvLyBzYW1wbGUgdmFyaWFuY2Ugb2YgbG9nIHByaWNlIAoKfQoKcGFyYW1ldGVycyB7CiAgcmVhbDxsb3dlcj0wPiBzaWdtYVNROwogIHJlYWwgYmV0YTA7CiAgcmVhbCBiZXRhMTsKfQoKdHJhbnNmb3JtZWQgcGFyYW1ldGVycyB7CiAgdmVjdG9yW1RdIG11OwogIGZvciAoaSBpbiAxOlQpIHsKICAgIG11W2ldID0gYmV0YTAgKyBiZXRhMSAqIGxjYXJbaV07CiAgfQoKfQoKbW9kZWwgewogIHNpZ21hU1EgfiBpbnZfZ2FtbWEoMC4wMSwgMC4wMSk7CiAgYmV0YTAgfiBub3JtYWwoMCwgMTAwKTsKICBiZXRhMSB+IG5vcm1hbCgwLCAxMDApOwoKICBmb3IgKGkgaW4gMTpUKQogICAgcHJbaV0gfiBsb2dub3JtYWwobXVbaV0sIHNxcnQoc2lnbWFTUSkpOwp9CmdlbmVyYXRlZCBxdWFudGl0aWVzIHsKICB2ZWN0b3JbVF0gbG9nX2xpazsKICB2ZWN0b3JbVF0geV9yZXA7CgogIC8vdmVjdG9yW1RdIGxpazsKICByZWFsIFJic3E7ICAgICAgICAgICAgICAvLyBnb29kbmVzcy1vZi1maXQKICBSYnNxID0gMSAtIHNpZ21hU1EvdjsKICAKICBmb3IgKGkgaW4gMTpUKSB7CiAgICBsb2dfbGlrW2ldID0gbG9nbm9ybWFsX2xwZGYocHJbaV0gfCBtdVtpXSwgc3FydChzaWdtYVNRKSk7CiAgICB5X3JlcFtpXSA9IGxvZ25vcm1hbF9ybmcobXVbaV0sIHNxcnQoc2lnbWFTUSkpOwogICAgLy9saWtbaV0gPSBleHAobG9nX2xpa1tpXSk7CiAgfQoKfQoiCgpUIDwtIGxlbmd0aChkZiRwcmljZSkKdiA9IHZhcihkZiRwcmljZSkKc2V0LnNlZWQoOTIpCgptb2RlbF9uYW1lID0gIk1vZGVsX0NfIgpzdGFuX2RhdF9DID0gbGlzdChUID0gVCwgcHIgPSBkZiRwcmljZSwgbGNhciA9IGRmJGxjYXJhdCwgdiA9IHYpCnJfZml0X0MgPSBzdGFuKG1vZGVsX2NvZGUgPSBzdGFuX21vZF9DLCBkYXRhID0gc3Rhbl9kYXRfQywgCiAgICAgICAgICAgICBpdGVyID0gNTAwMCwgY2hhaW5zID0gNCwgCiAgICAgICAgICAgICBjb250cm9sID0gbGlzdChtYXhfdHJlZWRlcHRoID0gMjEpKQoKI2ZpbGVfbmFtZSA9IHBhc3RlKG1vZGVsX25hbWUsIGFzLmNoYXJhY3RlcihTeXMuRGF0ZSgpKSwgIi5yZGEiLCBzZXA9IiIpCiNzZXR3ZCgnL1VzZXJzL0FNL0RvY3VtZW50cy9fQ1UgTWFzdGVycy8yMDIwIGZhbGwgQmF5ZXNpYW5fNzM5My9jb2RlL0JheWVzaWFuX1N0YXRpc3RpY3NfQ2xhc3NfQ29kZS9FeGFtX2NvZGUnKQojcmVhZFJEUyhyX2ZpdCwgZmlsZSA9ICIiKSAKI3NhdmVSRFMocl9maXQsIGZpbGUgPSBmaWxlX25hbWUsIGNvbXByZXNzID0gInh6IikgCgpzdW1tYXJ5KHJfZml0X0MsIHBhcnMgPSBjKCJzaWdtYVNRIiwgImJldGEwIiwgImJldGExIiksIHByb2IgPSBjKDAuMDI1LCAwLjk3NSkpJHN1bW1hcnkKCiNzc28gPC0gbGF1bmNoX3NoaW55c3RhbihyX2ZpdF9BKQoKYGBgCgpgYGB7ciBQcm9ibGVtIDUgTW9kZWwgRCwgaW5jbHVkZT1GQUxTRX0Kc3Rhbl9tb2RfRCA9ICIKZGF0YSB7CiAgaW50IFQ7CiAgdmVjdG9yW1RdIHByOyAgICAgLy8gIHByaWNlIAogIHZlY3RvcltUXSBsY2FyOyAgIC8vIGxvZyBjYXJhdCAKICB2ZWN0b3JbVF0gbm90aWM7ICAvLyAgbm90aWNlYWJsZSAKCiAgcmVhbDxsb3dlcj0wPiB2OyAgLy8gc2FtcGxlIHZhcmlhbmNlIG9mIGxvZyBwcmljZSAKCn0KCnBhcmFtZXRlcnMgewogIHJlYWw8bG93ZXI9MD4gc2lnbWFTUTsKICByZWFsIGJldGEwOwogIHJlYWwgYmV0YTE7CiAgcmVhbCBiZXRhMjsKfQoKdHJhbnNmb3JtZWQgcGFyYW1ldGVycyB7CiAgdmVjdG9yW1RdIG11OwogIGZvciAoaSBpbiAxOlQpIHsKICAgIG11W2ldID0gYmV0YTAgKyBiZXRhMSAqIGxjYXJbaV0gKyBiZXRhMiAqIG5vdGljW2ldOwogIH0KCn0KCm1vZGVsIHsKICBzaWdtYVNRIH4gaW52X2dhbW1hKDAuMDEsIDAuMDEpOwogIGJldGEwIH4gbm9ybWFsKDAsIDEwMCk7CiAgYmV0YTEgfiBub3JtYWwoMCwgMTAwKTsKICBiZXRhMiB+IG5vcm1hbCgwLCAxMDApOwoKCiAgZm9yIChpIGluIDE6VCkKICAgIHByW2ldIH4gbG9nbm9ybWFsKG11W2ldLCBzcXJ0KHNpZ21hU1EpKTsKfQpnZW5lcmF0ZWQgcXVhbnRpdGllcyB7CiAgdmVjdG9yW1RdIGxvZ19saWs7CiAgdmVjdG9yW1RdIHlfcmVwOwoKICAvL3ZlY3RvcltUXSBsaWs7CiAgcmVhbCBSYnNxOyAgICAgICAgICAgICAgLy8gZ29vZG5lc3Mtb2YtZml0CiAgUmJzcSA9IDEgLSBzaWdtYVNRL3Y7CiAgCiAgZm9yIChpIGluIDE6VCkgewogICAgbG9nX2xpa1tpXSA9IGxvZ25vcm1hbF9scGRmKHByW2ldIHwgbXVbaV0sIHNxcnQoc2lnbWFTUSkpOwogICAgeV9yZXBbaV0gPSBsb2dub3JtYWxfcm5nKG11W2ldLCBzcXJ0KHNpZ21hU1EpKTsKICAgIC8vbGlrW2ldID0gZXhwKGxvZ19saWtbaV0pOwogIH0KCn0KIgoKVCA8LSBsZW5ndGgoZGYkcHJpY2UpCnYgPSB2YXIoZGYkcHJpY2UpCnNldC5zZWVkKDkzKQoKbW9kZWxfbmFtZSA9ICJNb2RlbF9EXyIKc3Rhbl9kYXRfRCA9IGxpc3QoVCA9IFQsIHByID0gZGYkcHJpY2UsIGxjYXIgPSBkZiRsY2FyYXQsIAogICAgICAgICAgICAgICAgICBub3RpYyA9IGFzLmludGVnZXIoZGYkaW5jbHVzaW9ucyA9PSAibm90aWNlYWJsZSIpICwgdiA9IHYpCnJfZml0X0QgPSBzdGFuKG1vZGVsX2NvZGUgPSBzdGFuX21vZF9ELCBkYXRhID0gc3Rhbl9kYXRfRCwgCiAgICAgICAgICAgICBpdGVyID0gNTAwMCwgY2hhaW5zID0gNCwgCiAgICAgICAgICAgICBjb250cm9sID0gbGlzdChtYXhfdHJlZWRlcHRoID0gMjEpKQoKI2ZpbGVfbmFtZSA9IHBhc3RlKG1vZGVsX25hbWUsIGFzLmNoYXJhY3RlcihTeXMuRGF0ZSgpKSwgIi5yZGEiLCBzZXA9IiIpCiNzZXR3ZCgnL1VzZXJzL0FNL0RvY3VtZW50cy9fQ1UgTWFzdGVycy8yMDIwIGZhbGwgQmF5ZXNpYW5fNzM5My9jb2RlL0JheWVzaWFuX1N0YXRpc3RpY3NfQ2xhc3NfQ29kZS9FeGFtX2NvZGUnKQojcmVhZFJEUyhyX2ZpdCwgZmlsZSA9ICIiKSAKI3NhdmVSRFMocl9maXQsIGZpbGUgPSBmaWxlX25hbWUsIGNvbXByZXNzID0gInh6IikgCgpzdW1tYXJ5KHJfZml0X0QsIHBhcnMgPSBjKCJzaWdtYVNRIiwgImJldGEwIiwgImJldGExIiwgImJldGEyIiksIHByb2IgPSBjKDAuMDI1LCAwLjk3NSkpJHN1bW1hcnkKCiNzc28gPC0gbGF1bmNoX3NoaW55c3RhbihyX2ZpdF9BKQoKYGBgCgpgYGB7ciBQcm9ibGVtIDZhIFdBSUMvTE9PSUMsIGluY2x1ZGU9RkFMU0V9Cgp3YWljX2xvbyA9IGZ1bmN0aW9uIChmaXQpIHsKICBsb2dfbGlrID0gZXh0cmFjdF9sb2dfbGlrKGZpdCwgbWVyZ2VfY2hhaW5zID0gRkFMU0UpCiAgcl9lZmYgPSBleHAocmVsYXRpdmVfZWZmKGxvZ19saWspKQogIHdsID0gYyh3YWljKGxvZ19saWspJHdhaWMsIGxvbyhsb2dfbGlrLCByX2VmZiA9IHJfZWZmKSRsb29pYykKICByZXR1cm4od2wpCn0Kd2wgPSBhcnJheSgwLCBkaW09YygyLDMpLCAKICAgICAgICAgICBkaW1uYW1lcyA9IGxpc3QoYygiV0FJQyIsICJMT09JQyIpLCAKICAgICAgICAgICAgICAgICAgICAgICAgICAgYygiTW9kZWwgQiIsIk1vZGVsIEMiLCJNb2RlbCBEIikpKQp3bFsxLDFdID0gd2FpY19sb28ocl9maXRfQilbMV0Kd2xbMiwxXSA9IHdhaWNfbG9vKHJfZml0X0IpWzJdCndsWzEsMl0gPSB3YWljX2xvbyhyX2ZpdF9DKVsxXQp3bFsyLDJdID0gd2FpY19sb28ocl9maXRfQylbMl0Kd2xbMSwzXSA9IHdhaWNfbG9vKHJfZml0X0QpWzFdCndsWzIsM10gPSB3YWljX2xvbyhyX2ZpdF9EKVsyXQoKd2wKYGBgCgpgYGB7ciBQcm9ibGVtIDZiIGVmZmVjdHMgcGxvdHN9CnNhbXBsZXMgPSBleHRyYWN0KHJfZml0X0QpCm5jeWNsZXMgPSBsZW5ndGgoc2FtcGxlc1tbMV1dKQpUIDwtIGxlbmd0aChkZiRwcmljZSkKZGYkbm90aWMgPSBhcy5pbnRlZ2VyKGRmJGluY2x1c2lvbnMgPT0gIm5vdGljZWFibGUiKQoKIyBlYWNoIHJvdyBvZiB5cmVwIGlzIGEgc2FtcGxlIGZyb20gdGhlIHBwIGRpc3RyaWJ1dGlvbgp5cmVwID0gbWF0cml4KDAsIG5jb2wgPSBULCBucm93ID0gbmN5Y2xlcykKZm9yIChpIGluIHNlcV9sZW4oVCkpIHsKICBtdWkgPSBzYW1wbGVzJGJldGEwICsgc2FtcGxlcyRiZXRhMSAqIGRmJGxjYXJhdFtpXSArIHNhbXBsZXMkYmV0YTIgKiBkZiRub3RpY1tpXQogIHlyZXBbLCBpXSA9IHJsbm9ybShuY3ljbGVzLCBtZWFuID0gbXVpLCBzZCA9IHNxcnQoc2FtcGxlcyRzaWdtYVNRKSkKfQoKY29sb3Jfc2NoZW1lX3NldCgiYmx1ZSIpCnBwY19pbnRlcnZhbHNfZ3JvdXBlZCh5ID0gZGYkcHJpY2UsIHlyZXAgPSB5cmVwLCB4ID0gZGYkY2FyYXQsIHByb2IgPSAwLjUsIHByb2Jfb3V0ZXIgPSAuOTUsIGdyb3VwID0gZGYkbm90aWMpICsgZ2d0aXRsZSgiTW9kZWwgRDogUG9zdGVyaW9yIHByZWRpY3RpdmUgaW50ZXJ2YWxzIHRvIHRoZSBvYnNlcnZlZCBkYXRhIHZhbHVlcyIpICsgeGxhYigibGNhcmF0IikgKyB5bGFiKCJwcmljZSIpCgoKZmluZF9lcCA9IGZ1bmN0aW9uKHlyZXAsIG1pbiA9IDAuMSwgbWF4ID0gMi40LCBzdGVwPTAuMSkgewogIGVwID0gYXJyYXkoMCwgZGltPWMoKG1heC1taW4rc3RlcCkvc3RlcCwgNSksIGRpbW5hbWVzID0gbGlzdChjKCksIGMoImNhcmF0X21pbiIsICJjYXJhdF9tYXgiLCAiMi41JSIsIk1lYW4iLCI5Ny41JSIpKSkKICBuPTAKICBmb3IgKGkgaW4gc2VxKG1pbitzdGVwLCBtYXgsIGJ5PXN0ZXApKSB7CiAgICBuPW4rMQogICAgc3Vic2V0ID0gKChkZiRjYXJhdD4oaS1zdGVwKSkgJiAoZGYkY2FyYXQ8PWkpKQogICAgeXJlcF9zdWJzZXQgPSB5cmVwWyxzdWJzZXRdCiAgICBlcFtuLDFdID0gaS1zdGVwCiAgICBlcFtuLDJdID0gaQogICAgcSA9IHF1YW50aWxlKHlyZXBfc3Vic2V0LCBwcm9icyA9IGMoMC4wMjUsIDAuOTc1KSkKICAgIGVwW24sM10gPSBxW1sxXV0KICAgIGVwW24sNF0gPSBtZWFuKHlyZXBfc3Vic2V0KQogICAgZXBbbiw1XSA9IHFbWzJdXQogIH0KcmV0dXJuKGVwKQp9CgpmaW5kX2VwKHlyZXApCnRlbXAgPSBwcGNfaW50ZXJ2YWxzX2RhdGEoeSA9IGRmJHByaWNlLCB5cmVwID0geXJlcCwgeCA9IGRmJGxjYXJhdCwgcHJvYiA9IDAuNSwgcHJvYl9vdXRlciA9IC45NSwgZ3JvdXAgPSBkZiRub3RpYykKCmBgYAoKYGBge3IgUHJvYmxlbSA3X2EgTW9kZWwgRSwgaW5jbHVkZT1GQUxTRX0KCnN0YW5fbW9kX0UgPSAiCmRhdGEgewogIGludCBUOwogIGludCBkZWF0aHNbVF07IC8vIENPVklELTE5IGRlYXRocwogIHZlY3RvcltUXSBsb2dfcG9wOyAgICAvLyBsb2cgb2YgVS5TLiBzdGF0ZXMgcG9wdWxhdGlvbiwKICB2ZWN0b3JbVF0gaW5jb21lOyAvLyBtZWRpYW4gaW5jb21lIChVU0QpCiAgdmVjdG9yW1RdIGJzOyAgICAgLy8gcGVyY2VudGFnZSBvZiB0aGUgcG9wdWxhdGlvbiB3aXRoIGJhY2hlbG9y4oCZcyBkZWdyZWVzLgp9CgpwYXJhbWV0ZXJzIHsKICByZWFsIGJldGEwOwogIHJlYWwgYmV0YTE7CiAgcmVhbCBiZXRhMjsKfQoKbW9kZWwgewogIHJlYWwgbG9nX2xhbWJkYVtUXTsKCiAgYmV0YTAgfiBub3JtYWwoMCwgNSk7CiAgYmV0YTEgfiBub3JtYWwoMCwgNSk7CiAgYmV0YTIgfiBub3JtYWwoMCwgNSk7CiAKICBmb3IgKGkgaW4gMTpUKSB7CiAgICBsb2dfbGFtYmRhW2ldID0gbG9nX3BvcFtpXSArIGJldGEwICsgYmV0YTEgKiBpbmNvbWVbaV0gKyBiZXRhMiAqIGJzW2ldOwogICAgZGVhdGhzW2ldIH4gcG9pc3Nvbl9sb2cobG9nX2xhbWJkYVtpXSk7CiAgfQp9CgoiCgpUIDwtIGxlbmd0aChkZl9jb3ZpZCRicykKc2V0LnNlZWQoOTQpCgptb2RlbF9uYW1lID0gIk1vZGVsX0VfIgpzdGFuX2RhdF9FID0gbGlzdChUID0gVCwgZGVhdGhzID0gZGZfY292aWQkZGVhdGhzLCBsb2dfcG9wID0gbG9nKGRmX2NvdmlkJHBvcHVsYXRpb24pLCAKICAgICAgICAgICAgICAgICAgaW5jb21lID0gZGZfY292aWQkaW5jb21lLCBicyA9IGRmX2NvdmlkJGJzKQpyX2ZpdF9FID0gc3Rhbihtb2RlbF9jb2RlID0gc3Rhbl9tb2RfRSwgZGF0YSA9IHN0YW5fZGF0X0UsIAogICAgICAgICAgICAgaXRlciA9IDUwMDAwLCBjaGFpbnMgPSAyLCAKICAgICAgICAgICAgIGNvbnRyb2wgPSBsaXN0KG1heF90cmVlZGVwdGggPSAxNSkpCgpzdW1tYXJ5KHJfZml0X0UsIHBhcnMgPSBjKCJiZXRhMCIsICJiZXRhMSIsICJiZXRhMiIpLCBwcm9iID0gYygwLjAyNSwgMC45NzUpKSRzdW1tYXJ5Cgpzc28gPC0gbGF1bmNoX3NoaW55c3RhbihyX2ZpdF9FKQpmaWxlX25hbWUgPSBwYXN0ZShtb2RlbF9uYW1lLCBhcy5jaGFyYWN0ZXIoU3lzLkRhdGUoKSksICIucmRhIiwgc2VwPSIiKQpzZXR3ZCgnL1VzZXJzL0FNL0RvY3VtZW50cy9fQ1UgTWFzdGVycy8yMDIwIGZhbGwgQmF5ZXNpYW5fNzM5My9jb2RlL0JheWVzaWFuX1N0YXRpc3RpY3NfQ2xhc3NfQ29kZS9FeGFtX2NvZGUnKQojcmVhZFJEUyhyX2ZpdCwgZmlsZSA9ICIiKSAKc2F2ZVJEUyhyX2ZpdF9FLCBmaWxlID0gZmlsZV9uYW1lLCBjb21wcmVzcyA9ICJ4eiIpIApgYGAKCmBgYHtyIFByb2JsZW0gN19iIHJzdGFuYXJtIE1vZGVsIEUsIGluY2x1ZGU9RkFMU0V9CmRmX2NvdmlkX3JzdGFuID0gZGF0YS5mcmFtZShpbnQgPSAxLCAKICAgICAgICAgICAgICAgICAgICAgICAgICAgIGxvZ19wb3AgPSBsb2coZGZfY292aWQkcG9wdWxhdGlvbiksIAogICAgICAgICAgICAgICAgICAgICAgICAgICAgaW5jb21lID0gZGZfY292aWQkaW5jb21lLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgYnMgPSBkZl9jb3ZpZCRicykKbG9nKGRmX2NvdmlkJHBvcHVsYXRpb24pCm1vZF9yc3RhbmFybV9FID0gc3Rhbl9nbG0oZGVhdGhzIH4gaW50ICsgaW5jb21lICsgYnMsIAogICAgICAgICAgICAgICAgIG9mZnNldCA9IGxvZ19wb3AsCiAgICAgICAgICAgICAgICAgZmFtaWx5ID0gcG9pc3NvbihsaW5rID0gImxvZyIpLAogICAgICAgICAgICAgICAgIGRhdGEgPSBkZl9jb3ZpZF9yc3RhbiwKICAgICAgICAgICAgICAgICBpdGVyID0gMTAwMDAsIGNoYWlucyA9IDIpCmBgYAoKYGBgCgo=